package Leetcode.贪心;

import java.util.Arrays;
import java.util.Comparator;

class Activity {
    int start, finish;

    public Activity(int start, int finish) {
        this.start = start;
        this.finish = finish;
    }
}

public class ActivitySelection {

    public static void selectActivities(Activity[] activities) {
        // 按结束时间排序
        Arrays.sort(activities, Comparator.comparingInt(a -> a.finish));

        // 选择第一个活动
        System.out.println("选择的活动:");
        System.out.println("(" + activities[0].start + ", " + activities[0].finish + ")");

        int lastFinishTime = activities[0].finish;
        //当前活动开始时间是否晚于前面活动结束的时间
        for (int i = 1; i < activities.length; i++) {
            if (activities[i].start >= lastFinishTime) {
                System.out.println("(" + activities[i].start + ", " + activities[i].finish + ")");
                lastFinishTime = activities[i].finish;
            }
        }
    }

    public static void main(String[] args) {
        Activity[] activities = {
            new Activity(1, 3), new Activity(2, 5), new Activity(4, 6),
            new Activity(6, 8), new Activity(5, 7), new Activity(8, 9)
        };

        selectActivities(activities);
    }
}
/*
#include <stdio.h>
#include <stdlib.h>

// 定义活动结构体
typedef struct Activity {
    int start;
    int finish;
} Activity;

// 比较函数，用于排序
int compareActivities(const void *a, const void *b) {
    Activity *activityA = (Activity *)a;
    Activity *activityB = (Activity *)b;
    return activityA->finish - activityB->finish;
}

// 活动选择函数
void selectActivities(Activity activities[], int n) {
    // 使用qsort进行排序
    qsort(activities, n, sizeof(Activity), compareActivities);

    // 打印第一个活动
    printf("选择的活动:\n");
    printf("(%d, %d)\n", activities[0].start, activities[0].finish);

    // 上一个活动的结束时间
    int lastFinishTime = activities[0].finish;

    // 选择活动
    for (int i = 1; i < n; i++) {
        if (activities[i].start >= lastFinishTime) {
            printf("(%d, %d)\n", activities[i].start, activities[i].finish);
            lastFinishTime = activities[i].finish;
        }
    }
}

int main() {
    Activity activities[] = {
        {1, 3}, {2, 5}, {4, 6},
        {6, 8}, {5, 7}, {8, 9}
    };
    int n = sizeof(activities) / sizeof(activities[0]);

    selectActivities(activities, n);

    return 0;
}

 */
